package demo.practice.uf;

public class UFRankUnionPlant {

    int[] parent;
    int[] rank;//树的层数
    int plant;//株
    int maxLen;
    int[] len;

    public UFRankUnionPlant(int size) {
        parent = new int[size];
        rank = new int[size];
        len = new int[size];    //记录根的节点数
        plant = size;
        maxLen = 1;
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            rank[i] = 1;
            len[i] = 1;
        }
    }


    public int findP(int x) {//查询操作，其实是查询  根节点
        if (x < 0 || x >= parent.length)
            return -1;  //或者直接抛出异常

        while (parent[x] != x)//一直搜索到根节点
            x = parent[x];

        return x;
    }


    public void join(int a, int b) {
        int ap = findP(a);
        int bp = findP(b);
        if (ap != bp) {
            plant--;
            //a的层数越高，就将层数少的合并到层数高的上面
            int joinlen = len[ap] + len[bp];
            maxLen = Math.max(joinlen, maxLen);

            if (rank[ap] > rank[bp]) {
                parent[bp] = ap;
                len[ap] = joinlen;
            } else if (rank[ap] < rank[bp]) {
                parent[ap] = bp;
                len[bp] = joinlen;
            } else {
                //相同情况的话，随便就可以
                parent[ap] = bp;
                rank[bp]++;
                len[bp] = joinlen;
            }
        }
    }

    public int getPlant() {
        return plant;
    }

    public boolean isJoined(int a, int b) { //两个节点是否是  连接的
        return findP(a) == findP(b);
    }


}
